N Queens Problem using Backtracking
The N Queens Problem involves placing N chess queens on an N×N
chessboard so that no two queens threaten each other.
This means that no two queens can
share the same row, column, or diagonal. The problem is a classic example of backtracking, where
we explore all possible configurations to find valid solutions.
Video Lecture
Problem
Given an integer N, the goal is to find all distinct arrangements of N queens on an N×N
chessboard.
Each arrangement must satisfy the condition that no two queens can attack each
other. The process of arranging the queens is known as backtracking.
Input
An integer N representing the size of the chessboard and the number of queens to place.
Output
A list of all valid arrangements of the N queens on the chessboard.
Example:
- N = 4: Valid arrangements include:
- 1.
. Q . . . . . Q Q . . . . . Q .
- 2.
. . Q . Q . . . . . . Q . Q . .
Backtracking Approach
The backtracking algorithm systematically explores all possible placements of queens on the
board.
It builds solutions incrementally and abandons a solution as soon as it determines
that it cannot possibly lead to a valid configuration.
Steps to Solve N Queens Problem:
- Place Queens: Start placing queens one by one in different columns,
beginning from the first row.
- Check for Conflicts: After placing a queen, check if it leads to any
conflicts with previously placed queens.
- Backtrack if Necessary: If placing a queen leads to a conflict, backtrack
and try the next position.
- Store Valid Configurations: Once a valid configuration is found (i.e., all
N queens are placed without conflicts), store the arrangement.
This backtracking process continues until all possible configurations are explored, yielding all
valid solutions for the N Queens Problem.
Complexity
The time complexity of the backtracking algorithm for the N Queens Problem is O(N!), while the
space complexity is O(N) due to the recursive stack.
Problem
Given an integer N, the goal is to find all distinct arrangements of N queens on an N×N
chessboard.
Each arrangement must satisfy the condition that no two queens can attack each
other. The process of arranging the queens is known as backtracking.
Input
An integer N representing the size of the chessboard and the number of queens to place.
Output
A list of all valid arrangements of the N queens on the chessboard.
Example:
- N = 4: Valid arrangements include:
- 1.
. Q . . . . . Q Q . . . . . Q .
- 2.
. . Q . Q . . . . . . Q . Q . .
Backtracking Approach
The backtracking algorithm systematically explores all possible placements of queens on the
board.
It builds solutions incrementally and abandons a solution as soon as it determines
that it cannot possibly lead to a valid configuration.
Steps to Solve N Queens Problem:
- Place Queens: Start placing queens one by one in different columns, beginning from the first row.
- Check for Conflicts: After placing a queen, check if it leads to any conflicts with previously placed queens.
- Backtrack if Necessary: If placing a queen leads to a conflict, backtrack and try the next position.
- Store Valid Configurations: Once a valid configuration is found (i.e., all N queens are placed without conflicts), store the arrangement.
This backtracking process continues until all possible configurations are explored, yielding all valid solutions for the N Queens Problem.
Complexity
The time complexity of the backtracking algorithm for the N Queens Problem is O(N!), while the space complexity is O(N) due to the recursive stack.
N Queens Problem Algorithm
NQueens(N)
Input: An integer N representing the size of the chessboard and the
number of queens to place.
Output: All valid arrangements of N queens on an N×N chessboard.
Step 1: Start.
Step 2: Initialize an empty board of size N×N.
Step 3: Create a function placeQueen(row) that attempts to place a
queen in the specified row:
Step 4: If row == N, a valid arrangement is found. Store the
arrangement.
Step 5: For each column col in the current row:
Step 6: Check if placing a queen at (row, col) is safe
(no conflicts with previously placed queens):
Step 7: If it is safe, place the queen at
(row, col).
Step 8: Recursively call
placeQueen(row + 1) to attempt to place queens in the next row.
Step 9: If the recursive call returns, backtrack by
removing the queen from (row, col).
Step 10: Continue checking the next columns in the current row.
Step 11: Repeat Steps 4 to 10 until all possible placements are explored.
Step 12: Stop.
N Queens Problem using Backtracking code
#include <stdio.h>
#include <stdio.h>
#include <stdbool.h>
#define N 4 // Size of the chessboard (4x4)
// Function to print the board
void printBoard(int board[N][N]) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
printf("%d ", board[i][j]);
}
printf("\n");
}
printf("\n");
}
// Function to check if it's safe to place a queen at board[row][col]
bool isSafe(int board[N][N], int row, int col) {
int i, j;
// Check this row on the left side
for (i = 0; i < col; i++) {
if (board[row][i]) {
return false;
}
}
// Check the upper diagonal on the left side
for (i = row, j = col; i >= 0 && j >= 0; i--, j--) {
if (board[i][j]) {
return false;
}
}
// Check the lower diagonal on the left side
for (i = row, j = col; j >= 0 && i < N; i++, j--) {
if (board[i][j]) {
return false;
}
}
return true;
}
// Recursive function to solve the N-Queens problem
bool solveNQueens(int board[N][N], int col) {
// Base case: If all queens are placed
if (col >= N) {
printBoard(board); // Print the current solution
return true;
}
// Initialize flag to check if a solution is found
bool solutionFound = false;
// Try placing a queen in all rows for the current column
for (int i = 0; i < N; i++) {
if (isSafe(board, i, col)) {
// Place the queen
board[i][col] = 1;
// Recur to place the next queen
solutionFound = solveNQueens(board, col + 1) || solutionFound;
// Backtrack: Remove the queen
board[i][col] = 0;
}
}
return solutionFound;
}
// Main function
int main() {
int board[N][N] = { {0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0} };
// Start solving from the first column
if (!solveNQueens(board, 0)) {
printf("No solution found\n");
}
return 0;
}
#include
#define N 4 // Size of the chessboard (4x4)
using namespace std;
// Function to print the board
void printBoard(int board[N][N]) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cout < board[i][j] < " ";
}
cout < endl;
}
cout < endl;
}
// Function to check if it's safe to place a queen at board[row][col]
bool isSafe(int board[N][N], int row, int col) {
int i, j;
// Check this row on the left side
for (i = 0; i < col; i++) {
if (board[row][i]) {
return false;
}
}
// Check the upper diagonal on the left side
for (i = row, j = col; i >= 0 && j >= 0; i--, j--) {
if (board[i][j]) {
return false;
}
}
// Check the lower diagonal on the left side
for (i = row, j = col; j >= 0 && i < N; i++, j--) {
if (board[i][j]) {
return false;
}
}
return true;
}
// Recursive function to solve the N-Queens problem
bool solveNQueens(int board[N][N], int col) {
if (col >= N) {
printBoard(board);
return true;
}
bool solutionFound = false;
for (int i = 0; i < N; i++) {
if (isSafe(board, i, col)) {
board[i][col] = 1;
solutionFound = solveNQueens(board, col + 1) || solutionFound;
board[i][col] = 0; // Backtrack
}
}
return solutionFound;
}
// Main function
int main() {
int board[N][N] = { {0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0} };
if (!solveNQueens(board, 0)) {
cout < "No solution found" < endl;
}
return 0;
}
public class NQueens {
static final int N = 4; // Size of the chessboard (4x4)
// Function to print the board
static void printBoard(int board[][]) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
System.out.print(board[i][j] + " ");
}
System.out.println();
}
System.out.println();
}
// Function to check if it's safe to place a queen at board[row][col]
static boolean isSafe(int board[][], int row, int col) {
int i, j;
// Check this row on the left side
for (i = 0; i < col; i++) {
if (board[row][i] == 1) {
return false;
}
}
// Check the upper diagonal on the left side
for (i = row, j = col; i >= 0 && j >= 0; i--, j--) {
if (board[i][j] == 1) {
return false;
}
}
// Check the lower diagonal on the left side
for (i = row, j = col; j >= 0 && i < N; i++, j--) {
if (board[i][j] == 1) {
return false;
}
}
return true;
}
// Recursive function to solve the N-Queens problem
static boolean solveNQueens(int board[][], int col) {
if (col >= N) {
printBoard(board);
return true;
}
boolean solutionFound = false;
for (int i = 0; i < N; i++) {
if (isSafe(board, i, col)) {
board[i][col] = 1;
solutionFound = solveNQueens(board, col + 1) || solutionFound;
board[i][col] = 0; // Backtrack
}
}
return solutionFound;
}
public static void main(String[] args) {
int board[][] = { {0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0} };
if (!solveNQueens(board, 0)) {
System.out.println("No solution found");
}
}
}
N = 4 # Size of the chessboard (4x4)
# Function to print the board
def printBoard(board):
for row in board:
print(" ".join(str(x) for x in row))
print()
# Function to check if it's safe to place a queen at board[row][col]
def isSafe(board, row, col):
# Check this row on the left side
for i in range(col):
if board[row][i] == 1:
return False
# Check the upper diagonal on the left side
for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
if board[i][j] == 1:
return False
# Check the lower diagonal on the left side
for i, j in zip(range(row, N), range(col, -1, -1)):
if board[i][j] == 1:
return False
return True
# Recursive function to solve the N-Queens problem
def solveNQueens(board, col):
if col >= N:
printBoard(board)
return True
solutionFound = False
for i in range(N):
if isSafe(board, i, col):
board[i][col] = 1
solutionFound = solveNQueens(board, col + 1) or solutionFound
board[i][col] = 0 # Backtrack
return solutionFound
# Main function
if __name__ == "__main__":
board = [[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0]]
if not solveNQueens(board, 0):
print("No solution found")
Time Complexity of N Queens Problem
Time Complexity Basic Operation: Placement and Backtracking
Analysis
The time complexity of the N Queens problem using backtracking is O(N!). In the
worst case, we may have to place queens in every column for each row until a valid arrangement
is found or all possibilities are exhausted. Each queen placement requires checking for
conflicts with previously placed queens, which takes O(N) time.
Since there are N rows, and for each row, we may potentially explore N
columns, the number of arrangements can grow factorially. Hence, the overall time complexity of
the algorithm can be represented as:
T(N) = N * (N-1) * (N-2) * ... * 1 = O(N!)
However, due to the nature of backtracking, many arrangements can be pruned, leading to better
average-case performance, though the worst-case remains O(N!).